1. Field of the Invention
The present invention relates to a finite field multiplier used for implementing encrypting algorithm circuit, and more specifically, to a serial finite field multiplier for minimizing circuit power consumption and circuit area.
2. Description of the Prior Art
Portable type terminals such as a smart card and a smart phone comprise a microprocessor, an encrypting circuit, a memory, and input/output control circuits, etc. Since these portable type terminals have internationally standardized specifications for seamless interfaces with card reader systems, the terminals must be implemented with a minimum area in a limited space. Consequently, an encrypting circuit for implementing cryptography must be designed for low power consumption as well as small area.
An encrypting circuit such an elliptic curve cryptographic processor is implemented with multipliers, dividers, adders, and square operators on a finite field. The multipliers are used as the most basic operator among these operators. An operational equation in a finite field operation can be represented as a standard base, a normal base, or a dual base. Generally, the standard base representation is widely used because of its easy implementation. The polynomial base representation belongs to the standard base representation. A structure of a general multiplier on a polynomial base finite field is implemented with a bit-serial method or an array method. The array method can operate in a high speed, but it requires large hardware area for its implementation. As a result, a portable information terminal employs a structure according to the bit-serial method.
Ideas on the smart card and public-key cryptography have been around for 20 years. However, only a few years ago could the smart card employ the public-key cryptography by lack of method of implementing a public-key cryptography circuit suitable for IC (integrated circuit) cards. Recently, cryptographies such as RSA, US Digital Signature Standard, Russign Gost 34.10 have been frequently applied to the IC cards.
For the first time, W. Diffie and M. E. Hellman disclosed a concept of public-key cryptography suitable for a smart card in “New Directions in Cryptography” in 1976. Afterwards, the RSA cryptography which is based on the difficulty of factoring numbers was introduced in 1978 and has been still widely used. However, the RSA cryptography has a trend of extending over 1024 bits in order to increase its encryption strength, and has many difficulties in being mounted in a limited area such as smart cards. In 1987, Koblitz and Miller applied an ECC (Elliptic Curve Cryptography) algorithm to the public-key cryptography. Recently, the ECC algorithm has been used for implementing cryptography of the IC card such as smart cards because of its higher encryption strength with small bits.
Cryptographic processor employing the ECC algorithm comprises a finite field multipliers, dividers, adders and square operators. The multipliers play the most major role since the dividers and the square operators can be implemented with the multipliers. The finite field multipliers can be implemented in various ways. Typically, a serial multiplication structure such as an LFSR (Linear Feedback Shift Register) structure and a parallel multiplication structure such as a Systolic array structure are widely used for the finite field multipliers. Even though the LFSR structure has a slower multiplication speed than a parallel multiplication, the LFSR structure has wide usage because of its easy circuit implementation and capability of being implemented in small area.
The LFSR structure multiplier has been improved in various ways based on the method proposed by Edoardo D. Mastrovito. For example, a method has been proposed to overcome the shortcomings of slow operation speed of the serial multiplication of the LFSR structure. However, the proposed method has shortcomings of an increased circuit area because of its additional usage of t×m registers in order to achieve t times speed improvement.
Conventional finite field multipliers having LFSR structure comprise shift registers for storing the first input value, shift registers for storing the second input value, a plurality of logic gates for performing logic AND operations on the fist input value and the second input value, and registers for generating the multiplication result by adding the output value of each logic gate to the value of each bit and for storing the multiplication result.
The shift registers for storing the first input value and the second input value are implemented with flip-flops 1 to 3 as shown in FIG. 1. The flip-flops for each bit simultaneously perform shift operations in synchronization with each other in accordance with the main clock. Also, each of the registers for storing the multiplication results comprises flip-flop 6 as shown in FIG. 2.
Each of the flip-flops 1, 2, 3, 6 for each bit comprises first and second latches 4 and 5 as shown in FIG. 3, and transfers an input value to an output terminal at the clock edge. Each of the first and second latches 4 and 5 comprises a transistor Q1 for receiving an input value in accordance with the clock, and inverters I1 and I2 for latching an input value through a transistor Q2 operated by the clock.
A multiplication circuit having the aforementioned LFSR structure comprises a shift register having a shift function, AND gate, and XOR gate. The shift register comprises flip-flops synchronized at the edge of a clock. When the length of the multiplication data is m bits, 3×m flip-flops are needed in order to store the multiplication results. Since a single flip-flop comprises two latches, a total of 6×m latches are needed. Also, m AND gates and m+k XOR gates are needed, where k is the number of coefficients of 1 in an irreducible polynomial, that is, the number of feedback bits.
Registers constructed as above take up more than 60% of the total area and power consumption in a finite field multiplication circuit. Since flip-flops require twice as much area and power consumption as latches, there is a limitation in minimizing area and power consumption of a finite field multiplier under a restricted condition.